from typing import List


class Solution:
    # DFS 回溯算法
    # 时间复杂度：O(N*N!)
    # 空间复杂度：O(N*N!)
    #     递归树深度：O(log N)
    #     全排列个数：N!，每个全排列占空间 N
    # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        if n == 0: return res
        
        def dfs(path, used, depth):
            if depth == n:
                res.append(path[:])  # 全局只有一个 path 变量，因此这里需要拷贝
                return
            for i in range(n):  # 这里有个遍历的顺序，不会在撤销操作后重复搜索
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    dfs(path, used, depth+1)
                    used[i] = False  # 撤销操作，状态重置
                    path.pop()       # path 的变动只在尾部，因此为栈
        
        dfs(path=[], used=[False for _ in range(n)], depth=0)  # 全局只有一个 path 变量
        return res
    
    
    # DFS 回溯算法 + 剪枝 【比较巧妙】
    # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
    def permuteConcise(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        
        def backtrack(curr):
            if curr == n:
                res.append(nums[:])
            for i in range(curr, n):
                nums[curr], nums[i] = nums[i], nums[curr]
                backtrack(curr+1)
                nums[curr], nums[i] = nums[i], nums[curr]
        
        backtrack(0)
        return res
